package week10.Chapter12_优先队列与堆.Exp2;


import com.sun.javafx.tools.packager.TemplatePlaceholders;
import week10.Chapter12_优先队列与堆.Exp2.ExpressionTree;
import week10.Chapter12_优先队列与堆.Exp2.ExpressionTreeOp;
import week8.Chapter10_树.jsjf.BinaryTreeADT;
import week8.Chapter10_树.jsjf.BinaryTreeNode;
import week10.Chapter12_优先队列与堆.Exp2.LinkedBinaryTree;

import java.util.*;

/**
 * PostfixEvaluator this modification of our stack example uses a
 * stack to create an expression tree from a VALID integer postfix expression
 * and then uses a recursive method from the ExpressionTree class to
 * evaluate the tree.
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public class PostfixEvaluator
{
    private String expression;
    private Stack<ExpressionTree> treeStack;

    /**
     * Sets up this evalutor by creating a new stack.
     */
    public PostfixEvaluator()
    {
        treeStack = new Stack<ExpressionTree>();
    }

    /**
     * Retrieves and returns the next operand off of this tree stack.
     *
     * @param treeStack  the tree stack from which the operand will be returned
     * @return the next operand off of this tree stack
     */
    private ExpressionTree getOperand(Stack<ExpressionTree> treeStack)
    {
        ExpressionTree temp;
        temp = treeStack.pop();

        return temp;
    }

    /**
     * Evaluates the specified postfix expression by building and evaluating
     * an expression tree.
     *
     * @param expression string representation of a postfix expression
     * @return value of the given expression
     */
    public int evaluate(String expression)
    {
        ExpressionTree operand1, operand2;
        char operator;
        String tempToken;

        Scanner parser = new Scanner(expression);

        while (parser.hasNext())
        {
            tempToken = parser.next();
            operator = tempToken.charAt(0);

            if ((operator == '+') || (operator == '-') || (operator == '*') ||
                 (operator == '/'))
            {
                operand1 = getOperand(treeStack);
                operand2 = getOperand(treeStack);
                treeStack.push(new ExpressionTree
                                  (new ExpressionTreeOp(1,operator,0), operand2, operand1));
            }
            else
            {
                treeStack.push(new ExpressionTree(new ExpressionTreeOp
                                    (2,' ',Integer.parseInt(tempToken)), null, null));
            }

        }
        return (treeStack.peek()).evaluateTree();
    }
//    public LinkedBinaryTree BuBuild_Expression_Tree(String[] expression, int size){
//        LinkedBinaryTree linkedBinaryTree = new LinkedBinaryTree();
//        BinaryTreeNode binaryTreeNode = new BinaryTreeNode(null);
//        for (int i = expression.length-1; i > 0; i--){
//            if (expression[i].equals("+")||expression[i].equals("-")){
//                binaryTreeNode = new BinaryTreeNode(expression[i]);
//            }
//        }
//        return linkedBinaryTree;
//    }
    private boolean priority(String[] operator,int size){
        // 先对有+ - 的式子进行拆分
        boolean found1 = true,found2=true ,found = true;
        for (int i = 0 ; i< size;i++) {
            if (operator[i].equals("+")) {
                found1 = false;
            }
        }
        for (int i = 0 ; i< size;i++) {
            if (operator[i].equals("-")) {
                found2 = false;
                }
            }
        if (found1 == false||found2==false){
            found = false;
        }
        return found;
    }
    public BinaryTreeNode Build_Expression_Tree(String[] expression, int size){
        // 带括号的式子暂未实现（递归出现的问题太多了(╬￣皿￣)）
        BinaryTreeNode binaryTreeNode = new BinaryTreeNode(null);
        int length = size; //  元素个数
        String[] expression_Left_Tree = null; //  左子树
        String[] expression_Right_Tree = null; //  右子树
        for (int i = length - 1; i > 0; i--){  //  遍历数组元素
            String temp = expression[i];
//            if (priority(expression,expression.length)==0) {
                if (temp.equals("+") || temp.equals("-")) {  // 若遇到+ - ，则对数组进行此元素左右分割
                    binaryTreeNode = new BinaryTreeNode(temp);
                    expression_Left_Tree = new String[i];
                    expression_Right_Tree = new String[length - i - 1];
                    for (int j = 0; j < expression_Left_Tree.length; j++) {  //  拆分结点左边数组（左子树）
                        expression_Left_Tree[j] = expression[j];
                    }
                    for (int k = 0; k < expression_Right_Tree.length; k++) {//  拆分结点右边数组（右子树）
                        expression_Right_Tree[k] = expression[i + k + 1];
                    }
//                    if (expression_Left_Tree.length != 1) {
//                        binaryTreeNode.setLeft(Build_Expression_Tree(expression_Left_Tree, expression_Left_Tree.length));
//                        return binaryTreeNode;
//                    }
//                    if (expression_Right_Tree.length != 1) {
//                        binaryTreeNode.setRight(Build_Expression_Tree(expression_Right_Tree, expression_Right_Tree.length));
//                        return binaryTreeNode;
//                    }
                    if (expression_Left_Tree.length == 1) {  // 若结点左子树数组长度为1
                        binaryTreeNode.setLeft(new BinaryTreeNode(expression_Left_Tree[0]));// 输出数组元素并建立左孩子
                        if (expression_Right_Tree.length!=1){ // 对该结点右端进行建树，后面情况大致一样不做多余复述
                            binaryTreeNode.setRight(Build_Expression_Tree(expression_Right_Tree,expression_Right_Tree.length));
                        }
                        if (expression_Right_Tree.length==1){
                            binaryTreeNode.setRight(new BinaryTreeNode(expression_Right_Tree[0]));
                        }
                        return binaryTreeNode;

                    }


                    if (expression_Right_Tree.length == 1) {
                        binaryTreeNode.setRight(new BinaryTreeNode(expression_Right_Tree[0]));
                        if (expression_Left_Tree.length!=1){
                            binaryTreeNode.setLeft(Build_Expression_Tree(expression_Left_Tree,expression_Left_Tree.length));
                        }
                        if (expression_Left_Tree.length==1){
                            binaryTreeNode.setLeft(new BinaryTreeNode(expression_Left_Tree[0]));
                        }
                        return binaryTreeNode;
                    }
                    break;
                }
//            }

            else if (priority(expression,expression.length)!=false){  // 优先级判断，此刻数组里已无加减号
                if (temp.equals("*") || temp.equals("/")) {   // 若遇到+ - ，则对数组进行此元素左右分割
                    binaryTreeNode = new BinaryTreeNode(temp);
                    expression_Left_Tree = new String[i];
                    expression_Right_Tree = new String[length - i - 1];
                    for (int j = 0; j < expression_Left_Tree.length; j++) {
                        expression_Left_Tree[j] = expression[j];
                    }
                    for (int k = 0; k < expression_Right_Tree.length; k++) {
                        expression_Right_Tree[k] = expression[i + k + 1];
                    }
//                    if (expression_Left_Tree.length != 1) {
//                        binaryTreeNode.setLeft(Build_Expression_Tree(expression_Left_Tree, expression_Left_Tree.length));
//                        return binaryTreeNode;
//                    }
//                    if (expression_Right_Tree.length != 1) {
//                        binaryTreeNode.setRight(Build_Expression_Tree(expression_Right_Tree, expression_Right_Tree.length));
//                        return binaryTreeNode;
//                    }
                    if (expression_Left_Tree.length == 1) {
                        binaryTreeNode.setLeft(new BinaryTreeNode(expression_Left_Tree[0]));
                        if (expression_Right_Tree.length!=1){
                            binaryTreeNode.setRight(Build_Expression_Tree(expression_Right_Tree,expression_Right_Tree.length));
                        }
                        if (expression_Right_Tree.length==1){
                            binaryTreeNode.setRight(new BinaryTreeNode(expression_Right_Tree[0]));
                        }
                        return binaryTreeNode;
                    }
                    if (expression_Right_Tree.length == 1) {
                        binaryTreeNode.setRight(new BinaryTreeNode(expression_Right_Tree[0]));
                        if (expression_Left_Tree.length!=1){
                            binaryTreeNode.setLeft(Build_Expression_Tree(expression_Left_Tree,expression_Left_Tree.length));
                        }
                        if (expression_Left_Tree.length==1){
                            binaryTreeNode.setLeft(new BinaryTreeNode(expression_Left_Tree[0]));
                        }
                        return binaryTreeNode;
                    }
                    break;
                }
            }
        }
//        for (int scan = size - 1 ; scan > 0;scan--) {
//            String temp_operator = expression[scan];
//            if (temp_operator.equals("+") || temp_operator.equals("-")) {
//                break;
//            }
//            if (temp_operator.equals("*") || temp_operator.equals("/")) {
//                binaryTreeNode = new BinaryTreeNode(temp_operator);
//                expression_Left_Tree = new String[scan];
//                expression_Right_Tree = new String[length - scan - 1];
//                for (int j = 0; j < expression_Left_Tree.length; j++) {
//                    expression_Left_Tree[j] = expression[j];
//                }
//                for (int k = 0; k < expression_Right_Tree.length; k++) {
//                    expression_Right_Tree[k] = expression[scan + k + 1];
//                }
//            }
//            if (expression_Left_Tree.length == 1) {
//                binaryTreeNode.setLeft(new BinaryTreeNode(expression_Left_Tree[0]));
//                return binaryTreeNode;
//            }
//            if (expression_Right_Tree.length == 1) {
//                binaryTreeNode.setRight(new BinaryTreeNode(expression_Right_Tree[0]));
//                return binaryTreeNode;
//            }
//            break;
//        }
        binaryTreeNode.setLeft(Build_Expression_Tree(expression_Left_Tree,expression_Left_Tree.length));
        binaryTreeNode.setRight(Build_Expression_Tree(expression_Right_Tree,expression_Right_Tree.length));
        return binaryTreeNode;
    }




    //  通过中缀表达式求后缀表达式
//    public BinaryTreeNode Convert_Tree(String expression)
//    {
//        BinaryTreeNode binaryTreeNode = new BinaryTreeNode(null);
//        String[] temp_expression = expression.split(" ");
//        int length = temp_expression.length;
//        for (int i = length-1; i > 0; i--){
//            String ch = temp_expression[i];
//            if (ch.equals("+")||ch.equals("-")){
//                binaryTreeNode = new BinaryTreeNode(ch);
//            }
//            switch (ch){
//                case "+":
//                case "-":
//                    binaryTreeNode = new BinaryTreeNode(ch);
//
//
//
//
//
//                    break;
//                case "*":
//                case "/":
//                    binaryTreeNode = new BinaryTreeNode(ch);
//                    break;
//                default:
//                    if (binaryTreeNode.right==null){
//                        binaryTreeNode.setRight(new BinaryTreeNode(ch));
//                    }else {
//
//                        binaryTreeNode.setLeft(new BinaryTreeNode(ch));
//                    }
//
//            }
//        }
//
////        ExpressionTree operand1, operand2;
////        char operator;
////        String tempToken;
////
////        Scanner parser = new Scanner(expression);
////
////        while (parser.hasNext())
////        {
////            tempToken = parser.next();
////            operator = tempToken.charAt(0);
////
////            switch (operator){
////                case ' ':
////                    break;
////                case '(':
////                    treeStack.push(new ExpressionTree(new ExpressionTreeOp(2,'(',Integer.parseInt(tempToken)), null, null));
////                    break;
////                case '+':
////                case '-':
////                    while (!treeStack.empty()){
////                        treeStack.pop();
////                        if (treeStack.pop().getRoot().element=='('){
////
////                        }
////                    }
////            }
////            if ((operator == '+') || (operator == '-') || (operator == '*') ||
////                    (operator == '/'))
////            {
////                operand1 = getOperand(treeStack);
////                operand2 = getOperand(treeStack);
////                treeStack.push(new ExpressionTree(new ExpressionTreeOp(1,operator,0), operand2, operand1));
////            }
////            else
////            {
////                treeStack.push(new ExpressionTree(new ExpressionTreeOp(2,' ',Integer.parseInt(tempToken)), null, null));
////            }
////        }
//
//        return binaryTreeNode;
//    }
    /**
     * Returns the expression tree associated with this postfix evaluator.
     *
     * @return string representing the expression tree
     */
    public String getTree()
    {
        return (treeStack.peek()).printTree();
    }
}
